'''
https://www.nowcoder.com/practice/6dca0ebd48f94b4296fc11949e3a91b8?tpId=196&tqId=40415&ru=/exam/oj
'''
from typing import List


class Solution:
    # 归并
    def calArray(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)

        def smallSum(l, r):
            if l >= r: return 0
            m = (r + l) // 2
            return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m, r)

        def merge(l, m, r):
            # l ~ m
            ans = 0
            # 统计答案
            i, j, sum = l, m + 1, 0
            while j <= r:
                while i <= m and nums[i] <= nums[j]:
                    sum += nums[i]
                    i += 1
                ans += sum
                j += 1
            # 排序
            help = [0] * (r - l + 1)
            i, j, k = l, m + 1, 0
            while i <= m and j <= r:
                if nums[i] <= nums[j]:
                    help[k] = nums[i]
                    i += 1
                else:
                    help[k] = nums[j]
                    j += 1
                k += 1
            help[k:] = nums[i:m + 1] if i <= m else nums[j:r + 1]
            nums[l:r + 1] = help[:]
            return ans

        return smallSum(0, n - 1)


# arr = [1, 2, 3, 4, 5]
arr = [1,3,5,2,4,6]
res = Solution().calArray(arr)
print(res)